{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from scipy.spatial import distance_matrix\n",
    "from copy import copy\n",
    "from tqdm import tqdm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [],
   "source": [
    "def select_next_node_AEL(current_node, destination_node, unvisited_nodes, distance_matrix, threshold=0.7):\n",
    "    \"\"\"Algorithm Evolution Using Large Language Model\"\"\"\n",
    "    scores = {}\n",
    "    for node in unvisited_nodes:\n",
    "        all_distances = [distance_matrix[node][i] for i in unvisited_nodes if i != node]\n",
    "        average_distance_to_unvisited = np.mean(all_distances)\n",
    "        std_dev_distance_to_unvisited = np.std(all_distances)\n",
    "        score = 0.4 * distance_matrix[current_node][node] - 0.3 * average_distance_to_unvisited + 0.2 * std_dev_distance_to_unvisited - 0.1 * distance_matrix[destination_node][node]\n",
    "        scores[node] = score\n",
    "    if min(scores.values()) > threshold:\n",
    "        next_node = min(unvisited_nodes, key=lambda node: distance_matrix[current_node][node])\n",
    "    else:\n",
    "        next_node = min(scores, key=scores.get)\n",
    "    return next_node\n",
    "\n",
    "def select_next_node_ReEvo(current_node: int, destination_node: int, unvisited_nodes: set, distance_matrix: np.ndarray) -> int:\n",
    "    \"\"\"Select the next node to visit from the unvisited nodes.\"\"\"\n",
    "    weights = {'distance_to_current': 0.4, \n",
    "               'average_distance_to_unvisited': 0.25, \n",
    "               'std_dev_distance_to_unvisited': 0.25, \n",
    "               'distance_to_destination': 0.1}\n",
    "    scores = {}\n",
    "    for node in unvisited_nodes:\n",
    "        future_distances = [distance_matrix[node, i] for i in unvisited_nodes if i != node]\n",
    "        if future_distances:\n",
    "            average_distance_to_unvisited = sum(future_distances) / len(future_distances)\n",
    "            std_dev_distance_to_unvisited = (sum((x - average_distance_to_unvisited) ** 2 for x in future_distances) / len(future_distances)) ** 0.5\n",
    "        else:\n",
    "            average_distance_to_unvisited = std_dev_distance_to_unvisited = 0\n",
    "        score = (weights['distance_to_current'] * distance_matrix[current_node, node] -\n",
    "                 weights['average_distance_to_unvisited'] * average_distance_to_unvisited +\n",
    "                 weights['std_dev_distance_to_unvisited'] * std_dev_distance_to_unvisited -\n",
    "                 weights['distance_to_destination'] * distance_matrix[destination_node, node])\n",
    "        scores[node] = score\n",
    "    next_node = min(scores, key=scores.get)\n",
    "    return next_node\n",
    "\n",
    "def select_next_node_nearest(current_node, destination_node, unvisited_nodes, distance_matrix):\n",
    "    \"\"\"Nearest Neighbour\"\"\"\n",
    "    return min(unvisited_nodes, key=lambda node: distance_matrix[current_node][node])\n",
    "\n",
    "def eval_heuristic(node_positions: np.ndarray, select_next_node) -> float:\n",
    "    '''\n",
    "    Generate solution for TSP problem using the GPT-generated heuristic algorithm.\n",
    "    \n",
    "    Parameters\n",
    "    ----------\n",
    "    node_positions : np.ndarray\n",
    "        2D array of node positions of shape (problem_size, 2).\n",
    "    \n",
    "    Returns\n",
    "    -------\n",
    "    obj : float\n",
    "        The length of the generated tour.\n",
    "    '''\n",
    "    problem_size = node_positions.shape[0]\n",
    "    # calculate distance matrix\n",
    "    dist_mat = distance_matrix(node_positions, node_positions)\n",
    "    # set the starting node\n",
    "    start_node = 0\n",
    "    solution = [start_node]\n",
    "    # init unvisited nodes\n",
    "    unvisited = set(range(problem_size))\n",
    "    # remove the starting node\n",
    "    unvisited.remove(start_node)\n",
    "    # run the heuristic\n",
    "    for _ in range(problem_size - 1):\n",
    "        next_node = select_next_node(\n",
    "            current_node=solution[-1],\n",
    "            destination_node=start_node,\n",
    "            unvisited_nodes=unvisited,\n",
    "            distance_matrix=dist_mat,\n",
    "        )\n",
    "        solution.append(next_node)\n",
    "        if next_node in unvisited:\n",
    "            unvisited.remove(next_node)\n",
    "        else:\n",
    "            raise KeyError(f\"Node {next_node} is already visited.\")\n",
    "    \n",
    "    # calculate the length of the tour\n",
    "    obj = 0\n",
    "    for i in range(problem_size):\n",
    "        obj += dist_mat[solution[i], solution[(i + 1) % problem_size]]\n",
    "    return obj\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Evaluating heuristic for size 20 with 64 instances\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|██████████| 64/64 [00:00<00:00, 13567.62it/s]\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Average objective value for size 20: 4.446566634076893 \n",
      "\n",
      "Evaluating heuristic for size 50 with 64 instances\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|██████████| 64/64 [00:00<00:00, 4014.29it/s]\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Average objective value for size 50: 6.891886602053466 \n",
      "\n",
      "Evaluating heuristic for size 100 with 64 instances\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|██████████| 64/64 [00:00<00:00, 1152.30it/s]\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Average objective value for size 100: 9.650788327301203 \n",
      "\n",
      "Evaluating heuristic for size 200 with 64 instances\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|██████████| 64/64 [00:00<00:00, 310.52it/s]\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Average objective value for size 200: 13.424787407459862 \n",
      "\n",
      "Evaluating heuristic for size 500 with 64 instances\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|██████████| 64/64 [00:01<00:00, 50.19it/s]\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Average objective value for size 500: 20.65273146870541 \n",
      "\n",
      "Evaluating heuristic for size 1000 with 64 instances\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|██████████| 64/64 [00:04<00:00, 12.94it/s]"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Average objective value for size 1000: 29.178004049667557 \n",
      "\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "\n"
     ]
    }
   ],
   "source": [
    "for size in [20, 50, 100, 200, 500, 1000]:\n",
    "    # Load dataset\n",
    "    X = np.load('../dataset/test{}_dataset.npy'.format(size))\n",
    "    objs = []\n",
    "    print(\"Evaluating heuristic for size {} with {} instances\".format(size, len(X)))\n",
    "    for node_positions in tqdm(X):\n",
    "        obj = eval_heuristic(node_positions, select_next_node_nearest)\n",
    "        objs.append(obj)\n",
    "    print('Average objective value for size {}: {}'.format(size, np.mean(objs)), \"\\n\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Evaluating heuristic for size 20 with 64 instances\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "  0%|          | 0/64 [00:00<?, ?it/s]/Users/yhr/anaconda3/lib/python3.11/site-packages/numpy/core/fromnumeric.py:3464: RuntimeWarning: Mean of empty slice.\n",
      "  return _methods._mean(a, axis=axis, dtype=dtype,\n",
      "/Users/yhr/anaconda3/lib/python3.11/site-packages/numpy/core/_methods.py:192: RuntimeWarning: invalid value encountered in scalar divide\n",
      "  ret = ret.dtype.type(ret / rcount)\n",
      "/Users/yhr/anaconda3/lib/python3.11/site-packages/numpy/core/_methods.py:269: RuntimeWarning: Degrees of freedom <= 0 for slice\n",
      "  ret = _var(a, axis=axis, dtype=dtype, out=out, ddof=ddof,\n",
      "/Users/yhr/anaconda3/lib/python3.11/site-packages/numpy/core/_methods.py:226: RuntimeWarning: invalid value encountered in divide\n",
      "  arrmean = um.true_divide(arrmean, div, out=arrmean,\n",
      "/Users/yhr/anaconda3/lib/python3.11/site-packages/numpy/core/_methods.py:261: RuntimeWarning: invalid value encountered in scalar divide\n",
      "  ret = ret.dtype.type(ret / rcount)\n",
      "100%|██████████| 64/64 [00:00<00:00, 403.66it/s]\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Average objective value for size 20: 4.078671740854158 \n",
      "\n",
      "Evaluating heuristic for size 50 with 64 instances\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|██████████| 64/64 [00:01<00:00, 52.24it/s]\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Average objective value for size 50: 6.233106835234127 \n",
      "\n",
      "Evaluating heuristic for size 100 with 64 instances\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|██████████| 64/64 [00:06<00:00,  9.85it/s]\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Average objective value for size 100: 8.600976801785489 \n",
      "\n",
      "Evaluating heuristic for size 200 with 64 instances\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|██████████| 64/64 [00:38<00:00,  1.67it/s]\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Average objective value for size 200: 12.307232622768458 \n",
      "\n",
      "Evaluating heuristic for size 500 with 64 instances\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|██████████| 64/64 [07:55<00:00,  7.42s/it]\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Average objective value for size 500: 19.23704059951398 \n",
      "\n",
      "Evaluating heuristic for size 1000 with 64 instances\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|██████████| 64/64 [56:58<00:00, 53.41s/it]"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Average objective value for size 1000: 27.34434531143195 \n",
      "\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "\n"
     ]
    }
   ],
   "source": [
    "for size in [20, 50, 100, 200, 500, 1000]:\n",
    "    # Load dataset\n",
    "    X = np.load('../dataset/test{}_dataset.npy'.format(size))\n",
    "    objs = []\n",
    "    print(\"Evaluating heuristic for size {} with {} instances\".format(size, len(X)))\n",
    "    for node_positions in tqdm(X):\n",
    "        obj = eval_heuristic(node_positions, select_next_node_AEL)\n",
    "        objs.append(obj)\n",
    "    print('Average objective value for size {}: {}'.format(size, np.mean(objs)), \"\\n\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Evaluating heuristic for size 20 with 64 instances\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|██████████| 64/64 [00:00<00:00, 1328.55it/s]\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Average objective value for size 20: 4.090583020412613 \n",
      "\n",
      "Evaluating heuristic for size 50 with 64 instances\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|██████████| 64/64 [00:00<00:00, 114.89it/s]\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Average objective value for size 50: 6.2268621650994955 \n",
      "\n",
      "Evaluating heuristic for size 100 with 64 instances\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|██████████| 64/64 [00:04<00:00, 15.15it/s]\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Average objective value for size 100: 8.56755502424587 \n",
      "\n",
      "Evaluating heuristic for size 200 with 64 instances\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|██████████| 64/64 [00:32<00:00,  1.94it/s]\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Average objective value for size 200: 12.092696980562213 \n",
      "\n",
      "Evaluating heuristic for size 500 with 64 instances\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|██████████| 64/64 [08:22<00:00,  7.86s/it]\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Average objective value for size 500: 18.948248117331183 \n",
      "\n",
      "Evaluating heuristic for size 1000 with 64 instances\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|██████████| 64/64 [1:06:01<00:00, 61.90s/it]"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Average objective value for size 1000: 26.79167114037522 \n",
      "\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "\n"
     ]
    }
   ],
   "source": [
    "for size in [20, 50, 100, 200, 500, 1000]:\n",
    "    # Load dataset\n",
    "    X = np.load('../dataset/test{}_dataset.npy'.format(size))\n",
    "    objs = []\n",
    "    print(\"Evaluating heuristic for size {} with {} instances\".format(size, len(X)))\n",
    "    for node_positions in tqdm(X):\n",
    "        obj = eval_heuristic(node_positions, select_next_node_ReEvo)\n",
    "        objs.append(obj)\n",
    "    print('Average objective value for size {}: {}'.format(size, np.mean(objs)), \"\\n\")"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "base",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.3"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
